package algorithms.search;

import java.io.BufferedInputStream;
import java.util.Scanner;

/**
 * 红黑树
 * @author glogo
 *
 * @param <Key>
 * @param <Value>
 */
public class RedBlackBST<Key extends Comparable<Key>, Value> {

	private static final boolean RED = true;
	private static final boolean BLACK = false;
	
	private Node root;
	
	private class Node{
		Key key;
		Value val;
		Node left, right;
		int N;
		boolean color;	
		
		public Node(Key key, Value val, int N, boolean color) {
			this.key   = key;
			this.val   = val;
			this.N     = N;
			this.color = color;
		}
	}
	
	private boolean isRed(Node x){
		if(x == null)	return BLACK;
		return x.color == RED;
	}
	
	public int size(){
		return size(root);
	}
	
	
	private int size(Node x) {
		if(x == null)	return 0;
		return x.N;
	}

	private Node rotateLeft(Node h){
		Node x  = h.right;
		h.right = x.left;
		x.left  = h;
		x.color = h.color;
		h.color = RED;	
		x.N     = h.N;
		h.N     = 1 + size(h.left) + size(h.right);
		
		return x;
	}

	private Node rotateRight(Node h){
		Node x  = h.left;
		h.left  = x.right;
		x.right = h;
		x.color = h.color;
		h.color = RED;	
		x.N     = h.N;
		h.N     = 1 + size(h.left) + size(h.right);
		
		return x;
	}
	
	
	private void flipColors(Node h){
		h.color = !h.color;
        h.left.color = !h.left.color;
        h.right.color = !h.right.color;
	}
	
	public void put(Key key, Value val){
		root = put(root, key, val);
		root.color = BLACK;
	}
	
	/**
	 * 
	 * @param h 
	 * @param key 
	 * @param val 
	 * @return
	 */
	private Node put(Node h, Key key, Value val){
		if(h == null)
			return new Node(key, val, 1, RED);
		int cmp = key.compareTo(h.key);
		if(cmp < 0)	h.left = put(h.left, key, val);
		else if(cmp > 0) h.right = put(h.right, key, val);
		else h.val = val;
		
		if(isRed(h.right) && !isRed(h.left) ) h = rotateLeft(h);
		if(isRed(h.left) && isRed(h.left.right)) h = rotateRight(h);
		if(isRed(h.left) && isRed(h.right)) flipColors(h);
		
		h.N = size(h.left) + size(h.right) + 1;
		return h;
	}
	
	
	// restore red-black tree invariant
    private Node balance(Node h) {
//        assert (h != null);

        if (isRed(h.right))                      h = rotateLeft(h);
        if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
        if (isRed(h.left) && isRed(h.right))     flipColors(h);

        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

	public void deleteMin(){
		if(!isRed(root.left) && !isRed(root.right)){
			root.color = RED;
		}
		root = deleteMin(root);
		if(!isEmpty())	root.color = BLACK;
	}
	
    
	private Node deleteMin(Node h) {
		if(h.left == null)
			return null;
		if(!isRed(h.left) && !isRed(h.left.left))
			h = moveRedLeft(h.left);
		h.left = deleteMin(h.left);
		return balance(h);
	}

	private Node moveRedLeft(Node left) {
		return null;
	}

	private boolean isEmpty() {
		return root.N == 0;
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(new BufferedInputStream(System.in));
		RedBlackBST<String, Integer> st = new RedBlackBST<String, Integer>();
        for (int i = 0; i < 10 ; i++) {
            String key = scanner.nextLine();
            st.put(key, i);
        }
//        for (String s : st.keys())
//            System.out.println(s + " " + st.get(s));
        scanner.close();
	}
}
